#include<bits/stdc++.h>
using namespace std;
int nextarr[100];

void getnext(string s) {
	int j = 0, k = -1;
	nextarr[0] = -1;
	while (j < s.length()) {
		if (k == -1 || s[j] == s[k]) {
			j++;
			k++;
			nextarr[j] = k;
		}
		else {
			k = nextarr[k];
		}
	}
}

int KMP(string s, string t) {
	int i = 0, j = 0;
	int cnt = 0;
	while (i < s.length()) {
		if (j == -1 || s[i] == t[j]) {
			i++, j++;
		}
		else {
			j = nextarr[j];
		}
		if (j == t.length()) {
			cnt++;
			j = nextarr[j];
		}
	}
	return cnt;
}

int main() {
	string s = "aaabbdaabbde";
	string t = "aabbd";
	getnext(t);
	cout << KMP(s, t);
	return 0;
}
